// 78. 子集
// https://leetcode.cn/problems/subsets/

/**
示例 1：

输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
示例 2：

输入：nums = [0]
输出：[[],[0]]
 */

var subsets = function (nums) {
    let ret = [[]];

    for (let i = 1; i <= nums.length; i++) {
        for (let j = 0; j < nums.length; j++) {
            dfs(nums, i, j, 0, [], ret);
        }
    }

    console.log(JSON.stringify(ret));

    return ret;
};

function dfs(arr, max, index, level, acc, all) {
    if (acc.length == max || index + level >= arr.length) {
        return;
    }

    acc.push(arr[level + index]);

    for (let i = index; i < arr.length; i++) {
        let newAcc = JSON.parse(JSON.stringify(acc));
        if (level + 1 == max) {
            all.push(acc);
            break;
        }
        dfs(arr, max, i, level + 1, newAcc, all);
    }
}

// test
// 输入：nums = [1,2,3]
// 输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

subsets([1, 2, 3]);

// 输入：nums = [0]
// 输出：[[], [0]]
subsets([0]);
